Theory of Computation
Q121.
Consider the following finite automata P and Q over the alphabet {a, b, c}. The start states are indicated by a double arrow and final states are indicated by a double circle. Let the languages recognized by them be denoted by L(P) and L(Q) respectively.The automation which recognizes the language L(P)\capL(Q) is :Q122.
Given below are two finite state automata (\rightarrow indicates the start state and F indicates a final state) Which of the following represents the product automaton ZxY?Q123.
Match the following NFAs with the regular expressions they correspond to 1. \epsilon + 0(01*1 + 00) * 01* 2. \epsilon + 0(10 *1 + 00) * 0 3. \epsilon + 0(10 *1 + 10) *1 4. \epsilon + 0(10 *1 + 10) *10 *Q125.
Consider the following two finite automata. M_1 accepts L_1 and M_2 accepts L_2. Which one of the following is TRUE?Q126.
Consider the following DFA in which S_0 is the start state and S_1, S_3 are the final statesWhat language does this DFA recognize?Q127.
Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet \{Z_0, X\} where Z_0 is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X) \rightarrow (t, XZ_0) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z_0 and X (in that order) on the stack. (s, a, Z_0) \rightarrow (s, XXZ_0) (s, \epsilon, Z_0) \rightarrow (f, \epsilon) (s, a, X) \rightarrow (s, XXX) (s, b, X) \rightarrow (t, \epsilon) (t, b, X) \rightarrow (t,\epsilon) (t, c, X) \rightarrow (u, \epsilon) (u, c, X) \rightarrow (u, \epsilon) (u, \epsilon, Z_0) \rightarrow (f, \epsilon) The language accepted by the PDA isQ128.
In a pushdown automaton P=(Q, \Sigma, \Gamma, \delta, q_0, F), a transition of the form, where p,q \in Q \; a \in \sigma \cup \{ \epsilon \} ,\;X,Y, \in \Gamma \cup \{ \epsilon \}, represents(q,Y) \in \delta(p,a,X) Consider the following pushdown automaton over the input alphabet \Sigma = \{a,b\} and stack alphabet \Gamma = \{ \#, A\}. The number of strings of length 100 accepted by the above pushdown automaton is ___________Q130.
The language accepted by a Pushdown Automaton in which the stack is limited to 10 items is best described as